#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<algorithm>

using namespace std;

int findMinimumOperations(string s1, string s2, string s3) {
    int count = 0;
    int n = min(min(s1.size(), s2.size()), s3.size());
    for (int i = 0; i < n; i++)
    {
        if (s1[i] == s2[i] && s1[i] == s3[i])
        {
            count++;
        }
        else break;
    }
    int res = s1.size() - count + s2.size() - count + s3.size() - count;
    return res;
}

long long minimumSteps(string s) {
    int w = 0;
    for (int i = 0; i < s.size(); i++)
        if (s[i] == '0') w++;

    int count = 0;
    long long res = 0;
    for (int i = w - 1; i >= 0; i--)
    {
        if (s[i] == '1')
        {
            for (int j = s.size() - count; j >= w; j--)
            {
                if (s[j] == '0')
                {
                    res += j - i;
                    s[j] = '1';
                    break;
                }
                count++;
            }
        }
    }
    return res;
}

vector<int> leftmostBuildingQueries(vector<int>& heights, vector<vector<int>>& queries) {
    vector<vector<int>> vv(heights.size());
    map<int, vector<int>> s;
    for (int i = heights.size() - 1; i >= 0; i--)
    {
        auto pos = upper_bound(s.begin(), s.end(), make_pair(heights[i], vector<int>()), [](pair<int, vector<int>> a, pair<int, vector<int>> b) {
            return a.first < b.first;
            });
        while (pos != s.end())
        {
            int n = pos->second.size();
            for (int j = 0; j < n; j++)
                vv[i].push_back(pos->second[j]);
            pos++;
        }
        s[heights[i]].push_back(i);
    }

    for (int i = 0; i < vv.size(); i++)
        sort(vv[i].begin(), vv[i].end());
    vector<int> res(queries.size(), -1);
    for (int i = 0; i < queries.size(); i++)
    {
        int a = queries[i][0], b = queries[i][1];
        if (a == b)
        {
            res[i] = a;
            break;
        }

        set<int> un;
        un.insert(a);
        for (int j = 0; j < vv[a].size(); j++)
        {
            un.insert(vv[a][j]);
        }
            
        for (int j = 0; j < vv[b].size(); j++)
        {
            int t = vv[b][j];
            if (un.find(t) != un.end())
            {
                res[i] = t;
                break;
            }
        }

        if (un.find(b) != un.end())
        {
            if (res[i] == -1)    res[i] = b;
            else res[i] = min(res[i], b);
        }
    }
    return res;
}

int main()
{
    vector<int> v = { 5,3,8,2,6,1,4,6 };
    vector<vector<int>> vv = { {0,7},{3,5},{5,2},{3,0},{1,6} };
    leftmostBuildingQueries(v, vv);
	return 0;
}

